<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="chinese">
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">



  
  
    
      
    
    
      
    
  <script src="//cdn.jsdelivr.net/npm/pace-js@1/pace.min.js"></script>
  <link href="//cdn.jsdelivr.net/npm/pace-js@1/themes/blue/pace-theme-minimal.min.css" rel="stylesheet">







<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="Hexo, NexT">










<meta name="description" content="程序 = 数据结构 + 算法。虽然有些夸张，但足以说明数据结构与算法的重要性。 主要介绍以下4点：  从搜索树到 B+ 树，讲解与树有关的数据结构；  字符串匹配相关的题目；  算法面试经常考察的 TopK 问题；  算法题的几种常用解题方法。   大O推导法，对于算法来说，总的时间复杂度等于其中最大的时间复杂度。数据结构知识点：   队列和栈是经常用的数据结构。队列是先进先出，栈是后进后出。">
<meta name="keywords" content="Java Php hexo Thinking in Java">
<meta property="og:type" content="article">
<meta property="og:title" content="数据结构与算法">
<meta property="og:url" content="http://yoursite.com/2020/03/30/数据结构与算法/index.html">
<meta property="og:site_name" content="坚持就是胜利">
<meta property="og:description" content="程序 = 数据结构 + 算法。虽然有些夸张，但足以说明数据结构与算法的重要性。 主要介绍以下4点：  从搜索树到 B+ 树，讲解与树有关的数据结构；  字符串匹配相关的题目；  算法面试经常考察的 TopK 问题；  算法题的几种常用解题方法。   大O推导法，对于算法来说，总的时间复杂度等于其中最大的时间复杂度。数据结构知识点：   队列和栈是经常用的数据结构。队列是先进先出，栈是后进后出。">
<meta property="og:locale" content="chinese">
<meta property="og:image" content="http://yoursite.com/images/data_structure.png">
<meta property="og:image" content="http://yoursite.com/images/algorithm.png">
<meta property="og:image" content="http://yoursite.com/images/two_tree.png">
<meta property="og:image" content="http://yoursite.com/images/red_black_tree.png">
<meta property="og:image" content="http://yoursite.com/images/b_tree.png">
<meta property="og:image" content="http://yoursite.com/images/b+tree.png">
<meta property="og:image" content="http://yoursite.com/images/topkb.png">
<meta property="og:image" content="http://yoursite.com/images/fz.png">
<meta property="og:updated_time" content="2020-04-01T03:57:26.084Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="数据结构与算法">
<meta name="twitter:description" content="程序 = 数据结构 + 算法。虽然有些夸张，但足以说明数据结构与算法的重要性。 主要介绍以下4点：  从搜索树到 B+ 树，讲解与树有关的数据结构；  字符串匹配相关的题目；  算法面试经常考察的 TopK 问题；  算法题的几种常用解题方法。   大O推导法，对于算法来说，总的时间复杂度等于其中最大的时间复杂度。数据结构知识点：   队列和栈是经常用的数据结构。队列是先进先出，栈是后进后出。">
<meta name="twitter:image" content="http://yoursite.com/images/data_structure.png">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":14,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '190coder'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://yoursite.com/2020/03/30/数据结构与算法/">





  <title>数据结构与算法 | 坚持就是胜利</title>
  








</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="chinese">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">坚持就是胜利</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle"></p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br>
            
            Home
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br>
            
            Categories
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
            
            Archives
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/03/30/数据结构与算法/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="190coder">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="坚持就是胜利">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">数据结构与算法</h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2020-03-30T17:49:21+08:00">
                2020-03-30
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">In</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/计算机基础/" itemprop="url" rel="index">
                    <span itemprop="name">计算机基础</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>程序 = 数据结构 + 算法。虽然有些夸张，但足以说明数据结构与算法的重要性。 主要介绍以下4点：</p>
<ol>
<li><p>从搜索树到 B+ 树，讲解与树有关的数据结构；</p>
</li>
<li><p>字符串匹配相关的题目；</p>
</li>
<li><p>算法面试经常考察的 TopK 问题；</p>
</li>
<li><p>算法题的几种常用解题方法。</p>
</li>
</ol>
<p><strong>大O推导法，对于算法来说，总的时间复杂度等于其中最大的时间复杂度。</strong><br><strong>数据结构知识点：</strong></p>
<p><img src="/images/data_structure.png" alt></p>
<ol>
<li><p>队列和栈是经常用的数据结构。队列是先进先出，栈是后进后出。</p>
</li>
<li><p>表，包括很多种，有占用连续空间的数组、用指针链接的单向和双向链表，首尾相接的循环链表、以及散列表，也叫哈希表。 </p>
</li>
<li><p>图，在特定领域使用的比较多，例如路由算法中会经常使用到，图分为有向图、无向图及带权图，这部分需要掌握图的深度遍历和广度遍历算法，了解最短路径算法。</p>
</li>
<li><p>树的内容，树一般用作查找与排序的辅助结构，剩下两个部分都和树有关，一个是二叉树，一个是多叉树。</p>
<ul>
<li>多叉树包括 B 树族，有 B 树、B+ 树、B* 树，比较适合用来做文件检索；另外一个是字典树，适合进行字符串的多模匹配。</li>
<li>二叉树包括平衡二叉树、红黑树、哈夫曼树，以及堆，适合用于进行数据查找和排序。这部分需要了解二叉树的构建、插入、删除操作的实现，需要掌握二叉树的前序、中序、后序遍历。</li>
</ul>
</li>
</ol>
<p><strong>算法知识点:</strong></p>
<p><img src="/images/algorithm.png" alt></p>
<ol>
<li>算法题的常用算法解题方法。</li>
<li>复杂度是衡量算法好坏的标准之一，我们需要掌握计算算法时间复杂度和空间复杂度的方法。计算时间复杂度的方法一般是找到执行次数最多的语句，然后计算语句执行次数的数量级，最后用大写 O 来表示结果。</li>
<li>常用的字符串匹配算法，了解不同算法的匹配思路。 </li>
<li>排序也是经常考察的知识点，排序算法分为插入、交换、选择、归并、基数五类，其中快速排序和堆排序考察的频率最高，要重点掌握，需要能够手写算法实现。</li>
<li>常用的查找算法，包括二分查找、二叉排序树、B树、Hash、BloomFilter等，需要了解它们的适用场景，例如二分查找适合小数量集内存查找，B树适合文件索引，Hash常数级的时间复杂度更适合对查找效率要求较高的场合，BloomFilter 适合对大数据集进行数据存在性过滤。</li>
</ol>
<h2 id="一、详解二叉搜索树"><a href="#一、详解二叉搜索树" class="headerlink" title="一、详解二叉搜索树"></a>一、详解二叉搜索树</h2><h4 id="1-二叉搜索树"><a href="#1-二叉搜索树" class="headerlink" title="1. 二叉搜索树"></a>1. 二叉搜索树</h4><p><img src="/images/two_tree.png" alt><br>二叉树的查询时间复杂度是 log(N)，但是随着不断的插入、删除节点，二叉树的树高可能会不断变大，当一个二叉搜索树所有节点都只有左子树或者都只有右子树时，其查找性能就退化成线性的了。</p>
<h4 id="2-平衡二叉树"><a href="#2-平衡二叉树" class="headerlink" title="2. 平衡二叉树"></a>2. 平衡二叉树</h4><p>平衡二叉树可以解决上面这个问题，平衡二叉树保证每个节点左右子树的高度差的绝对值不超过1，例如AVL树。AVL树是严格的平衡二叉树，插入或删除数据时可能经常需要旋转来保持平衡，插入或删除数据时可能经常需要旋转来保持平衡，比较适合插入、删除比较少的场景。</p>
<h4 id="3-红黑树"><a href="#3-红黑树" class="headerlink" title="3. 红黑树"></a>3. 红黑树</h4><p> 红黑树是一种更加实用的非严格的平衡二叉树。红黑树更关注局部平衡而非整体平衡，确保没有一条路径会比其他路径长出 2 倍，所以是接近平衡的，但减少了许多不必要的旋转操作，更加实用。Java 8 的 HashMap 中就应用了红黑树来解决散列冲突时的查找问题。TreeMap 也是通过红黑树来保证有序性的。<br> 红黑树除了拥有二叉搜索树的特点外，还有以下规则，如下图所示。</p>
<p><img src="/images/red_black_tree.png" alt></p>
<ul>
<li>每个节点不是红色就是黑色</li>
<li>根结点是黑色</li>
<li>每个叶子节点（NIL）都是黑色空节点</li>
<li>红色节点的两个子节点都是黑色的</li>
<li>任意节点到器叶节点的每条路径上，包含相同数量的黑色节点</li>
</ul>
<h4 id="4-B-树-（B-树）"><a href="#4-B-树-（B-树）" class="headerlink" title="4. B 树 （B- 树）"></a>4. B 树 （B- 树）</h4><p>一种多叉树，也叫多路搜索树。B 树中每个节点可以存储多个元素，非常适合用在文件索引上，可以有效减少磁盘 IO 次数。B 树中所有结点的最大子节点数称为 B 树的阶，如下图所示是一棵 3 阶 B 树，也叫 2-3 树。</p>
<p><img src="/images/b_tree.png" alt></p>
<p>一个m阶B树有如下特点：</p>
<pre><code>- 非叶节点最多有m棵子树
- 根节点最少有两个子树，非根、非叶子节点最少有m/2棵子树
- 非叶子结点中保存的关键字个数，等于该节点子树个数−1，就是说一个节点如果有 3棵子树，那么其中必定包含 2 个关键字；（节点中的数字是关键字）
- 非叶子节点中的关键字大小有序，如上图中左边的节点中 37、51 两个元素就是有序的；
- 节点中每个关键字的左子树中的关键字都小于该关键字，右子树中的关键字都大于该关键字。如上图中关键字 51 的左子树有 42、49，都小于 51，右子树的节点有 59，大于51；
- 所有叶节点都在同一层。</code></pre><p>B 树在查找时，从根结点开始，对结点内的有序的关键字序列进行二分查找，如果找到就结束，没有找到就进入查询关键字所属范围的子树进行查找，直到叶节点。B 树一般应用在文件系统。<strong>4 阶 B 树表示每个节点最多有 4 个子树、3 个关键字，最少有 2 个子树、一个关键字，超过关键字限制需要拆分</strong></p>
<h4 id="5-B-树"><a href="#5-B-树" class="headerlink" title="5. B+ 树"></a>5. B+ 树</h4><p><img src="/images/b+tree.png" alt><br>B+ 树的定义与 B 树基本相同，除了下面这几个特点。</p>
<pre><code>- 节点中的关键字与子树数目相同，比如节点中有 3 个关键字，那么就有 3 棵子树；
- 关键字对应的子树中的节点都大于或等于关键字，子树中包括关键字自身；
- 所有关键字都出现在叶子节点中；
- 所有叶子节点都有指向下一个叶子节点的指针。</code></pre><p>与 B 树不同，<strong>B+ 树在搜索时不会在非叶子节点命中，一定会查询到叶子节点；另外一个，叶子节点相当于数据存储层，保存关键字对应的数据，而非叶子节点只保存关键字和指向叶节点的指针，不保存关键字对应的数据，所以同样数量关键字的非叶节点，B+ 树比 B 树要小很多。</strong></p>
<p>B+ 树更适合索引系统，MySQL 数据库的索引就提供了 B+ 树实现。原因有三个：</p>
<pre><code>- 由于叶节点之间有指针相连，B+ 树更适合范围检索；
- 由于非叶节点只保存关键字和指针，同样大小非叶节点，B+ 树可以容纳更多的关键字，可以降低树高，查询时磁盘读写代价更低；
- B+ 树的查询效率比较稳定。任何关键字的查找必须走一条从根结点到叶子结点的路，所有关键字查询的路径长度相同，效率相当。</code></pre><p>还有一种 B* 树的变种，在 B+ 树的非叶节点上，也增加了指向同一层下一个非叶节点的指针。</p>
<h2 id="二、字符串匹配"><a href="#二、字符串匹配" class="headerlink" title="二、字符串匹配"></a>二、字符串匹配</h2><h4 id="1-字符串匹配问题"><a href="#1-字符串匹配问题" class="headerlink" title="1. 字符串匹配问题"></a>1. 字符串匹配问题</h4><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br></pre></td><td class="code"><pre><span class="line">public class Main &#123;</span><br><span class="line"></span><br><span class="line">    public static boolean isMatch(String str)&#123;</span><br><span class="line"></span><br><span class="line">        HashMap bucket = new HashMap();</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">        bucket.put(&apos;)&apos;,&apos;(&apos;);</span><br><span class="line">        bucket.put(&apos;]&apos;,&apos;[&apos;);</span><br><span class="line">        bucket.put(&apos;&#125;&apos;,&apos;&#123;&apos;);</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">        Stack&lt;Character&gt; characterStack = new Stack&lt;&gt;();</span><br><span class="line">        for(Character cs : str.toCharArray())&#123;</span><br><span class="line"></span><br><span class="line">            characterStack.empty();</span><br><span class="line">            if(bucket.containsValue(cs))&#123;</span><br><span class="line">                characterStack.push(cs);</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">            else if(bucket.containsKey(cs))&#123;</span><br><span class="line">                System.out.println(characterStack);</span><br><span class="line">                System.out.println(cs);</span><br><span class="line"></span><br><span class="line">                if(characterStack.empty()||characterStack.pop()!= bucket.get(cs))&#123;</span><br><span class="line"></span><br><span class="line">                    return  false;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        return characterStack.empty();</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    public static void main(String[] args)</span><br><span class="line">    &#123;</span><br><span class="line"></span><br><span class="line">        String content = &quot;(我是中国人)&quot;;</span><br><span class="line">        System.out.println(isMatch(content));</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="三、-排序"><a href="#三、-排序" class="headerlink" title="三、 排序"></a>三、 排序</h2><h4 id="1-TopK-问题"><a href="#1-TopK-问题" class="headerlink" title="1.TopK 问题"></a>1.TopK 问题</h4><p>解决思路：用前k个数创建大小为k的根堆，剩余N-K个数组和堆顶进行比较</p>
<p><strong>对于n个数，取Top k个数，时间复杂度为O(nlogk)，这样在n较大情况下，是优于nlogn的时间复杂度的。</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br></pre></td><td class="code"><pre><span class="line">package com.company;</span><br><span class="line"></span><br><span class="line">import java.util.*;</span><br><span class="line"></span><br><span class="line">public class TopK&lt;E extends Comparable&gt; &#123;</span><br><span class="line"></span><br><span class="line">    private PriorityQueue&lt;E&gt; queue;</span><br><span class="line">    private int maxSize; //堆的最大容量</span><br><span class="line"></span><br><span class="line">    public TopK(int maxSize) &#123;</span><br><span class="line">        if (maxSize &lt;= 0) &#123;</span><br><span class="line">            throw new IllegalStateException();</span><br><span class="line">        &#125;</span><br><span class="line">        this.maxSize = maxSize;</span><br><span class="line">        this.queue = new PriorityQueue&lt;&gt;(maxSize, new Comparator&lt;E&gt;() &#123;</span><br><span class="line">            @Override</span><br><span class="line">            public int compare(E o1, E o2) &#123;</span><br><span class="line">                // 最大堆用o2 - o1，最小堆用o1 - o2</span><br><span class="line">                return (o1.compareTo(o2));</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    public void add(E e) &#123;</span><br><span class="line">        if (queue.size() &lt; maxSize) &#123;</span><br><span class="line"></span><br><span class="line">            queue.add(e);</span><br><span class="line">        &#125; else &#123;</span><br><span class="line">            E peek = queue.peek();</span><br><span class="line">            if (e.compareTo(peek) &gt; 0) &#123;</span><br><span class="line">                queue.poll();</span><br><span class="line">                queue.add(e);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    public List&lt;E&gt; sortedList() &#123;</span><br><span class="line">        List&lt;E&gt; list = new ArrayList&lt;&gt;(queue);</span><br><span class="line">        Collections.sort(list);</span><br><span class="line">        return list;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    public static void main(String[] args) &#123;</span><br><span class="line">        int[] array = &#123;4, 5, 1, 6, 2, 7, 3, 8&#125;;</span><br><span class="line">        TopK pq = new TopK(4);</span><br><span class="line">        for (int n : array) &#123;</span><br><span class="line">            pq.add(n);</span><br><span class="line">        &#125;</span><br><span class="line">        System.out.println(pq.sortedList());</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="2-TopK-变种问题"><a href="#2-TopK-变种问题" class="headerlink" title="2. TopK 变种问题"></a>2. TopK 变种问题</h4><p>TopK 变种的问题，就是从 N 个有序队列中，找到最小或者最大的 K 个值。这个问题的不同点在于，是对多个数据集进行排序。由于初始的数据集是有序的，因此不需要遍历完 N 个队列中所有的元素。因此，解题思路是如何减少要遍历的元素。<br><img src="/images/topkb.png" alt></p>
<h2 id="三、常用算法"><a href="#三、常用算法" class="headerlink" title="三、常用算法"></a>三、常用算法</h2><h4 id="1-分治法"><a href="#1-分治法" class="headerlink" title="1. 分治法"></a>1. 分治法</h4><p>分治法的思想是将一个难以直接解决的复杂问题或者大问题，分割成一些规模较小的相同问题，分而治之。比如快速排序、归并排序等都是应用了分治法。</p>
<p><img src="/images/fz.png" alt></p>
<h4 id="2-动态规划法"><a href="#2-动态规划法" class="headerlink" title="2. 动态规划法"></a>2. 动态规划法</h4><p>动态规划法，与分治法类似，也是将问题分解为多个子问题。与分治法不同的是，子问题的解之间是有关联的。前一子问题的解，为后一子问题的求解提供了有用的信息。动态规划法依次解决各子问题，在求解每一个子问题时，列出所有局部解，通过决策保留那些有可能达到全局最优的局部解。最后一个子问题的解就是初始问题的解。</p>
<h4 id="4-贪心算法"><a href="#4-贪心算法" class="headerlink" title="4. 贪心算法"></a>4. 贪心算法</h4><p>第三个贪心算法，因为它考虑的是局部的最优解，所以贪心算法不是对所有问题都能得到整体最优解。贪心算法的关键是贪心策略的选择。贪心策略必须具备无后效性，就是说某个状态以后的过程不会影响以前的状态，只与当前状态有关。</p>

      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2020/03/30/Java-JVM/" rel="next" title="Java JVM">
                <i class="fa fa-chevron-left"></i> Java JVM
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2020/04/02/spring-框架/" rel="prev" title="spring 框架">
                spring 框架 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            Table of Contents
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            Overview
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image" src="/images/avatar.jpg" alt="190coder">
            
              <p class="site-author-name" itemprop="name">190coder</p>
              <p class="site-description motion-element" itemprop="description">坚信持续学习就一定能超过大多数人</p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">53</span>
                  <span class="site-state-item-name">posts</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">13</span>
                  <span class="site-state-item-name">categories</span>
                </a>
              </div>
            

            

          </nav>

          

          

          
          

          
          

          <div style>
  <canvas id="canvas" style="width:60%;">当前浏览器不支持canvas，请更换浏览器后再试</canvas>
</div>
<script>
(function(){

   var digit=
    [
        [
            [0,0,1,1,1,0,0],
            [0,1,1,0,1,1,0],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [0,1,1,0,1,1,0],
            [0,0,1,1,1,0,0]
        ],//0
        [
            [0,0,0,1,1,0,0],
            [0,1,1,1,1,0,0],
            [0,0,0,1,1,0,0],
            [0,0,0,1,1,0,0],
            [0,0,0,1,1,0,0],
            [0,0,0,1,1,0,0],
            [0,0,0,1,1,0,0],
            [0,0,0,1,1,0,0],
            [0,0,0,1,1,0,0],
            [1,1,1,1,1,1,1]
        ],//1
        [
            [0,1,1,1,1,1,0],
            [1,1,0,0,0,1,1],
            [0,0,0,0,0,1,1],
            [0,0,0,0,1,1,0],
            [0,0,0,1,1,0,0],
            [0,0,1,1,0,0,0],
            [0,1,1,0,0,0,0],
            [1,1,0,0,0,0,0],
            [1,1,0,0,0,1,1],
            [1,1,1,1,1,1,1]
        ],//2
        [
            [1,1,1,1,1,1,1],
            [0,0,0,0,0,1,1],
            [0,0,0,0,1,1,0],
            [0,0,0,1,1,0,0],
            [0,0,1,1,1,0,0],
            [0,0,0,0,1,1,0],
            [0,0,0,0,0,1,1],
            [0,0,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [0,1,1,1,1,1,0]
        ],//3
        [
            [0,0,0,0,1,1,0],
            [0,0,0,1,1,1,0],
            [0,0,1,1,1,1,0],
            [0,1,1,0,1,1,0],
            [1,1,0,0,1,1,0],
            [1,1,1,1,1,1,1],
            [0,0,0,0,1,1,0],
            [0,0,0,0,1,1,0],
            [0,0,0,0,1,1,0],
            [0,0,0,1,1,1,1]
        ],//4
        [
            [1,1,1,1,1,1,1],
            [1,1,0,0,0,0,0],
            [1,1,0,0,0,0,0],
            [1,1,1,1,1,1,0],
            [0,0,0,0,0,1,1],
            [0,0,0,0,0,1,1],
            [0,0,0,0,0,1,1],
            [0,0,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [0,1,1,1,1,1,0]
        ],//5
        [
            [0,0,0,0,1,1,0],
            [0,0,1,1,0,0,0],
            [0,1,1,0,0,0,0],
            [1,1,0,0,0,0,0],
            [1,1,0,1,1,1,0],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [0,1,1,1,1,1,0]
        ],//6
        [
            [1,1,1,1,1,1,1],
            [1,1,0,0,0,1,1],
            [0,0,0,0,1,1,0],
            [0,0,0,0,1,1,0],
            [0,0,0,1,1,0,0],
            [0,0,0,1,1,0,0],
            [0,0,1,1,0,0,0],
            [0,0,1,1,0,0,0],
            [0,0,1,1,0,0,0],
            [0,0,1,1,0,0,0]
        ],//7
        [
            [0,1,1,1,1,1,0],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [0,1,1,1,1,1,0],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [0,1,1,1,1,1,0]
        ],//8
        [
            [0,1,1,1,1,1,0],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [0,1,1,1,0,1,1],
            [0,0,0,0,0,1,1],
            [0,0,0,0,0,1,1],
            [0,0,0,0,1,1,0],
            [0,0,0,1,1,0,0],
            [0,1,1,0,0,0,0]
        ],//9
        [
            [0,0,0,0,0,0,0],
            [0,0,1,1,1,0,0],
            [0,0,1,1,1,0,0],
            [0,0,1,1,1,0,0],
            [0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0],
            [0,0,1,1,1,0,0],
            [0,0,1,1,1,0,0],
            [0,0,1,1,1,0,0],
            [0,0,0,0,0,0,0]
        ]//:
    ];

var canvas = document.getElementById('canvas');

if(canvas.getContext){
    var cxt = canvas.getContext('2d');
    //声明canvas的宽高
    var H = 100,W = 700;
    canvas.height = H;
    canvas.width = W;
    cxt.fillStyle = '#f00';
    cxt.fillRect(10,10,50,50);

    //存储时间数据
    var data = [];
    //存储运动的小球
    var balls = [];
    //设置粒子半径
    var R = canvas.height/20-1;
    (function(){
        var temp = /(\d)(\d):(\d)(\d):(\d)(\d)/.exec(new Date());
        //存储时间数字，由十位小时、个位小时、冒号、十位分钟、个位分钟、冒号、十位秒钟、个位秒钟这7个数字组成
        data.push(temp[1],temp[2],10,temp[3],temp[4],10,temp[5],temp[6]);
    })();

    /*生成点阵数字*/
    function renderDigit(index,num){
        for(var i = 0; i < digit[num].length; i++){
            for(var j = 0; j < digit[num][i].length; j++){
                if(digit[num][i][j] == 1){
                    cxt.beginPath();
                    cxt.arc(14*(R+2)*index + j*2*(R+1)+(R+1),i*2*(R+1)+(R+1),R,0,2*Math.PI);
                    cxt.closePath();
                    cxt.fill();
                }
            }
        }
    }

    /*更新时钟*/
    function updateDigitTime(){
        var changeNumArray = [];
        var temp = /(\d)(\d):(\d)(\d):(\d)(\d)/.exec(new Date());
        var NewData = [];
        NewData.push(temp[1],temp[2],10,temp[3],temp[4],10,temp[5],temp[6]);
        for(var i = data.length-1; i >=0 ; i--){
            //时间发生变化
            if(NewData[i] !== data[i]){
                //将变化的数字值和在data数组中的索引存储在changeNumArray数组中
                changeNumArray.push(i+'_'+(Number(data[i])+1)%10);
            }
        }
        //增加小球
        for(var i = 0; i< changeNumArray.length; i++){
            addBalls.apply(this,changeNumArray[i].split('_'));
        }
        data = NewData.concat();
    }

    /*更新小球状态*/
    function updateBalls(){
        for(var i = 0; i < balls.length; i++){
            balls[i].stepY += balls[i].disY;
            balls[i].x += balls[i].stepX;
            balls[i].y += balls[i].stepY;
            if(balls[i].x > W + R || balls[i].y > H + R){
                balls.splice(i,1);
                i--;
            }
        }
    }

    /*增加要运动的小球*/
    function addBalls(index,num){
        var numArray = [1,2,3];
        var colorArray =  ["#3BE","#09C","#A6C","#93C","#9C0","#690","#FB3","#F80","#F44","#C00"];
        for(var i = 0; i < digit[num].length; i++){
            for(var j = 0; j < digit[num][i].length; j++){
                if(digit[num][i][j] == 1){
                    var ball = {
                        x:14*(R+2)*index + j*2*(R+1)+(R+1),
                        y:i*2*(R+1)+(R+1),
                        stepX:Math.floor(Math.random() * 4 -2),
                        stepY:-2*numArray[Math.floor(Math.random()*numArray.length)],
                        color:colorArray[Math.floor(Math.random()*colorArray.length)],
                        disY:1
                    };
                    balls.push(ball);
                }
            }
        }
    }

    /*渲染*/
    function render(){
        //重置画布宽度，达到清空画布的效果
        canvas.height = 100;
        //渲染时钟
        for(var i = 0; i < data.length; i++){
            renderDigit(i,data[i]);
        }
        //渲染小球
        for(var i = 0; i < balls.length; i++){
            cxt.beginPath();
            cxt.arc(balls[i].x,balls[i].y,R,0,2*Math.PI);
            cxt.fillStyle = balls[i].color;
            cxt.closePath();
            cxt.fill();
        }
    }

    clearInterval(oTimer);
    var oTimer = setInterval(function(){
        //更新时钟
        updateDigitTime();
        //更新小球状态
        updateBalls();
        //渲染
        render();
    },50);
}

})();
</script>



        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#一、详解二叉搜索树"><span class="nav-number">1.</span> <span class="nav-text">一、详解二叉搜索树</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#1-二叉搜索树"><span class="nav-number">1.0.1.</span> <span class="nav-text">1. 二叉搜索树</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#2-平衡二叉树"><span class="nav-number">1.0.2.</span> <span class="nav-text">2. 平衡二叉树</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#3-红黑树"><span class="nav-number">1.0.3.</span> <span class="nav-text">3. 红黑树</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#4-B-树-（B-树）"><span class="nav-number">1.0.4.</span> <span class="nav-text">4. B 树 （B- 树）</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#5-B-树"><span class="nav-number">1.0.5.</span> <span class="nav-text">5. B+ 树</span></a></li></ol></li></ol><li class="nav-item nav-level-2"><a class="nav-link" href="#二、字符串匹配"><span class="nav-number">2.</span> <span class="nav-text">二、字符串匹配</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#1-字符串匹配问题"><span class="nav-number">2.0.1.</span> <span class="nav-text">1. 字符串匹配问题</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#三、-排序"><span class="nav-number">3.</span> <span class="nav-text">三、 排序</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#1-TopK-问题"><span class="nav-number">3.0.1.</span> <span class="nav-text">1.TopK 问题</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#2-TopK-变种问题"><span class="nav-number">3.0.2.</span> <span class="nav-text">2. TopK 变种问题</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#三、常用算法"><span class="nav-number">4.</span> <span class="nav-text">三、常用算法</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#1-分治法"><span class="nav-number">4.0.1.</span> <span class="nav-text">1. 分治法</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#2-动态规划法"><span class="nav-number">4.0.2.</span> <span class="nav-text">2. 动态规划法</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#4-贪心算法"><span class="nav-number">4.0.3.</span> <span class="nav-text">4. 贪心算法</span></a></li></ol></li></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

	
           
         
         <div style>
  <canvas id="canvas" style="width:60%;">当前浏览器不支持canvas，请更换浏览器后再试</canvas>
</div>
<script>
(function(){

   var digit=
    [
        [
            [0,0,1,1,1,0,0],
            [0,1,1,0,1,1,0],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [0,1,1,0,1,1,0],
            [0,0,1,1,1,0,0]
        ],//0
        [
            [0,0,0,1,1,0,0],
            [0,1,1,1,1,0,0],
            [0,0,0,1,1,0,0],
            [0,0,0,1,1,0,0],
            [0,0,0,1,1,0,0],
            [0,0,0,1,1,0,0],
            [0,0,0,1,1,0,0],
            [0,0,0,1,1,0,0],
            [0,0,0,1,1,0,0],
            [1,1,1,1,1,1,1]
        ],//1
        [
            [0,1,1,1,1,1,0],
            [1,1,0,0,0,1,1],
            [0,0,0,0,0,1,1],
            [0,0,0,0,1,1,0],
            [0,0,0,1,1,0,0],
            [0,0,1,1,0,0,0],
            [0,1,1,0,0,0,0],
            [1,1,0,0,0,0,0],
            [1,1,0,0,0,1,1],
            [1,1,1,1,1,1,1]
        ],//2
        [
            [1,1,1,1,1,1,1],
            [0,0,0,0,0,1,1],
            [0,0,0,0,1,1,0],
            [0,0,0,1,1,0,0],
            [0,0,1,1,1,0,0],
            [0,0,0,0,1,1,0],
            [0,0,0,0,0,1,1],
            [0,0,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [0,1,1,1,1,1,0]
        ],//3
        [
            [0,0,0,0,1,1,0],
            [0,0,0,1,1,1,0],
            [0,0,1,1,1,1,0],
            [0,1,1,0,1,1,0],
            [1,1,0,0,1,1,0],
            [1,1,1,1,1,1,1],
            [0,0,0,0,1,1,0],
            [0,0,0,0,1,1,0],
            [0,0,0,0,1,1,0],
            [0,0,0,1,1,1,1]
        ],//4
        [
            [1,1,1,1,1,1,1],
            [1,1,0,0,0,0,0],
            [1,1,0,0,0,0,0],
            [1,1,1,1,1,1,0],
            [0,0,0,0,0,1,1],
            [0,0,0,0,0,1,1],
            [0,0,0,0,0,1,1],
            [0,0,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [0,1,1,1,1,1,0]
        ],//5
        [
            [0,0,0,0,1,1,0],
            [0,0,1,1,0,0,0],
            [0,1,1,0,0,0,0],
            [1,1,0,0,0,0,0],
            [1,1,0,1,1,1,0],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [0,1,1,1,1,1,0]
        ],//6
        [
            [1,1,1,1,1,1,1],
            [1,1,0,0,0,1,1],
            [0,0,0,0,1,1,0],
            [0,0,0,0,1,1,0],
            [0,0,0,1,1,0,0],
            [0,0,0,1,1,0,0],
            [0,0,1,1,0,0,0],
            [0,0,1,1,0,0,0],
            [0,0,1,1,0,0,0],
            [0,0,1,1,0,0,0]
        ],//7
        [
            [0,1,1,1,1,1,0],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [0,1,1,1,1,1,0],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [0,1,1,1,1,1,0]
        ],//8
        [
            [0,1,1,1,1,1,0],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [1,1,0,0,0,1,1],
            [0,1,1,1,0,1,1],
            [0,0,0,0,0,1,1],
            [0,0,0,0,0,1,1],
            [0,0,0,0,1,1,0],
            [0,0,0,1,1,0,0],
            [0,1,1,0,0,0,0]
        ],//9
        [
            [0,0,0,0,0,0,0],
            [0,0,1,1,1,0,0],
            [0,0,1,1,1,0,0],
            [0,0,1,1,1,0,0],
            [0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0],
            [0,0,1,1,1,0,0],
            [0,0,1,1,1,0,0],
            [0,0,1,1,1,0,0],
            [0,0,0,0,0,0,0]
        ]//:
    ];

var canvas = document.getElementById('canvas');

if(canvas.getContext){
    var cxt = canvas.getContext('2d');
    //声明canvas的宽高
    var H = 100,W = 700;
    canvas.height = H;
    canvas.width = W;
    cxt.fillStyle = '#f00';
    cxt.fillRect(10,10,50,50);

    //存储时间数据
    var data = [];
    //存储运动的小球
    var balls = [];
    //设置粒子半径
    var R = canvas.height/20-1;
    (function(){
        var temp = /(\d)(\d):(\d)(\d):(\d)(\d)/.exec(new Date());
        //存储时间数字，由十位小时、个位小时、冒号、十位分钟、个位分钟、冒号、十位秒钟、个位秒钟这7个数字组成
        data.push(temp[1],temp[2],10,temp[3],temp[4],10,temp[5],temp[6]);
    })();

    /*生成点阵数字*/
    function renderDigit(index,num){
        for(var i = 0; i < digit[num].length; i++){
            for(var j = 0; j < digit[num][i].length; j++){
                if(digit[num][i][j] == 1){
                    cxt.beginPath();
                    cxt.arc(14*(R+2)*index + j*2*(R+1)+(R+1),i*2*(R+1)+(R+1),R,0,2*Math.PI);
                    cxt.closePath();
                    cxt.fill();
                }
            }
        }
    }

    /*更新时钟*/
    function updateDigitTime(){
        var changeNumArray = [];
        var temp = /(\d)(\d):(\d)(\d):(\d)(\d)/.exec(new Date());
        var NewData = [];
        NewData.push(temp[1],temp[2],10,temp[3],temp[4],10,temp[5],temp[6]);
        for(var i = data.length-1; i >=0 ; i--){
            //时间发生变化
            if(NewData[i] !== data[i]){
                //将变化的数字值和在data数组中的索引存储在changeNumArray数组中
                changeNumArray.push(i+'_'+(Number(data[i])+1)%10);
            }
        }
        //增加小球
        for(var i = 0; i< changeNumArray.length; i++){
            addBalls.apply(this,changeNumArray[i].split('_'));
        }
        data = NewData.concat();
    }

    /*更新小球状态*/
    function updateBalls(){
        for(var i = 0; i < balls.length; i++){
            balls[i].stepY += balls[i].disY;
            balls[i].x += balls[i].stepX;
            balls[i].y += balls[i].stepY;
            if(balls[i].x > W + R || balls[i].y > H + R){
                balls.splice(i,1);
                i--;
            }
        }
    }

    /*增加要运动的小球*/
    function addBalls(index,num){
        var numArray = [1,2,3];
        var colorArray =  ["#3BE","#09C","#A6C","#93C","#9C0","#690","#FB3","#F80","#F44","#C00"];
        for(var i = 0; i < digit[num].length; i++){
            for(var j = 0; j < digit[num][i].length; j++){
                if(digit[num][i][j] == 1){
                    var ball = {
                        x:14*(R+2)*index + j*2*(R+1)+(R+1),
                        y:i*2*(R+1)+(R+1),
                        stepX:Math.floor(Math.random() * 4 -2),
                        stepY:-2*numArray[Math.floor(Math.random()*numArray.length)],
                        color:colorArray[Math.floor(Math.random()*colorArray.length)],
                        disY:1
                    };
                    balls.push(ball);
                }
            }
        }
    }

    /*渲染*/
    function render(){
        //重置画布宽度，达到清空画布的效果
        canvas.height = 100;
        //渲染时钟
        for(var i = 0; i < data.length; i++){
            renderDigit(i,data[i]);
        }
        //渲染小球
        for(var i = 0; i < balls.length; i++){
            cxt.beginPath();
            cxt.arc(balls[i].x,balls[i].y,R,0,2*Math.PI);
            cxt.fillStyle = balls[i].color;
            cxt.closePath();
            cxt.fill();
        }
    }

    clearInterval(oTimer);
    var oTimer = setInterval(function(){
        //更新时钟
        updateDigitTime();
        //更新小球状态
        updateBalls();
        //渲染
        render();
    },50);
}

})();
</script>



    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">190coder</span>

  
</div>


  <div class="powered-by">Powered by <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a></div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">Theme &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Gemini</a> v5.1.4</div>





<div>
    <script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    <span id="busuanzi_container_site_pv">本站总访问量<span id="busuanzi_value_site_pv"></span>次</span>
    <span class="post-meta-divider">|</span>
    <span id="busuanzi_container_site_uv">本站访客数<span id="busuanzi_value_site_uv"></span>人</span>
</div>


        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  


  











  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  

  
  
    <script type="text/javascript" src="//cdn.jsdelivr.net/gh/theme-next/theme-next-canvas-nest@1/canvas-nest.min.js"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.4"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.4"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  












  





  

  

  

  
  

  

  

  

</body>
</html>
